from typing import List


class Solution:
    """
    方法：回溯法
    Args:
        n: 整数，表示范围 [1, n]
        k: 整数，表示组合的长度
    Returns:
        List[List[int]]: 所有可能的 k 个数的组合
    Time: O(C(n,k) * k)，其中 C(n,k) 是组合数，k 是复制路径的时间
    Space: O(k)，递归栈的深度最多为 k
    """
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []
        def backtrack(i: int) -> None:
            d = k - len(path)
            if len(path) == k:
                ans.append(path.copy())
                return
            for j in range(i, d - 1, -1):
                path.append(j)
                backtrack(j-1)
                path.pop()
        backtrack(n)
        return ans
            
